1. Field of the Invention
The present invention relates generally to data encoding and transmission technology, and is applicable to wireless communication systems and apparatuses, specifically, short-range acoustic-based communication systems and apparatuses.
2. Description of the Related Art
FIG. 1 illustrates object transmission in a conventional bidirectional communication system employing an Automatic Repeat Request (ARQ) scheme.
In the conventional communication system, a transmitter 1 decomposes an information object such as a file or a message, into data packets and encodes each decomposed packet, typically by using a certain type of Forward Error Correction (FEC) coding. The packets encoded by the transmitter 1 are then modulated, and packetized information is transmitted to a receiver 2 over a communication channel (for example, acoustic channel). In order to achieve information transmission with high reliability through a communication medium with low reliability, the conventional communication system may use an ARQ protocol. In such a protocol, the receiver 2 transmits an acknowledgement message to the transmitter 1 in order to indicate that it has correctly received a data packet. If a packet has not been correctly received, then the receiver 2 may transmit a retransmission request message to the transmitter 1. Alternatively, the transmitter 1 may attempt retransmission if there has been no acknowledgement from the receiver 1 within a specified time-out.
Modern variants of the ARQ protocol include ARQ with Chase combining and ARQ with incremental redundancy, which do not need to discard unsuccessfully received packets, but instead, request complimentary packets and attempt to combine several unsuccessfully received packets in the receiver 2. See, for example G. Caire and D. Tuninetti, The Throughput of Hybrid-ARQ protocols for the Gaussian collision channel, IEEE Trans. on Inform. Theory, Vol. 47, No. 5, pp. 1971-1988, July 2001.
Nonetheless, in all ARQ-based schemes, it is necessary that there is a feedback communication path from a receiver to a transmitter, which can be used to transmit acknowledgement messages or retransmission requests. However, in some applications, it is difficult to implement the feedback channel because of several limiting factors. In acoustic connectivity applications, for example, the transmitter may have no capability to capture acoustical signals (for example, no microphone present), or the receiver may have no sound emitting capability, and others. In such cases, alternative schemes should be used that do not rely on the presence of a feedback communication path. Specifically, two types of schemes may be used. The first scheme is known as “broadcast carousel”. For example, see Paila, T., Luby, M., Lehtonen, R., Roca, V and R. Walsh: FLUTE-File Delivery over Unidirectional Transport. RFC 3926, October 2004] or [ETSI TS 101 498, Digital Audio Broadcasting (DAB); Broadcast website.
FIG. 2 illustrates object transmission in a conventional unidirectional communication system employing a broadcast carousel scheme.
In this scheme, the packets of the original message (i.e., an information object) are cyclically repeated in a loop (indefinitely) by means of transmission from a transmitter 3, and each packet has its unique identifier (number). A cyclic packet stream transmitted from the transmitter 3 to a receiver 4 includes a series of packets, such as “ . . . , packet 1, packet 2, packet 3, packet 1, packet 2, packet 3, packet 1, packet 2, . . . ”.
In a reliable communication channel, the receiver can collect all packets within a single loop regardless of the time of initial acquisition. If errors are introduced into the channel, then the receiver may still collect all data, but usually has to wait several “carousel” loops. As channel conditions gets worse, the broadcast carousel becomes less and less efficient. This is because in this scheme, if the receiver misses identical packets on consecutive carousel cycles, then it has to wait the full cycle for the next opportunity.
More sophisticated relevant technology uses so called “digital fountain codes”. These codes may be acquired from erasure codes such as Reed-Solomon codes, or may be more efficiently and flexibly implemented with Luby Transform (LT) codes or Raptor codes See, for example, D. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2005, Chapter 50.
FIG. 3 illustrates object transmission in a conventional communication system employing digital fountain codes.
In this coding scheme, a transmitter 5 transmits a long series of unique packets generated by digital fountain codes, such as Reed-Solomon code, LT codes, or Raptor codes. Once a receiver 6 successfully receives and collects a predefined number of packets, the transmitter 5 can decode the entire message (that is, information object). The receiver 6 continues to receive packets until a minimum number of packets are collected, and then perform reconstruction. This scheme has an advantage of higher efficiency than in channels with packet losses.
In contrast, the present invention provides a system for acoustic-based connectivity between mobile devices. This type of channel is known to have many challenges, such as a high background noise level, distortions, and an unpredictable and variable signal-to-noise ratio. As mentioned above, the conventional techniques have several drawbacks, which include: ARQ schemes and their variants require a feedback channel that may not be available in some applications or may be too complex to implement; A broadcast carousel is not effective in channels in to which packet errors are frequently introduced; and LT codes or Raptor codes are almost optimal in channels with packet losses (such as Internet communication or satellite broadcasting), but may be ineffective in channels with an unpredictable signal-to-noise ratio, such as acoustic communication between mobile devices. This is because, on one hand, in very poor channel conditions, most packets may be received with errors and thus shall not provide any useful information to a decoder, or conversely, in good channel conditions, all packets may be received with significant noise margins and therefore channel capacity shall not be fully utilized by such a system.
In order to solve this problem, an improved transmission scheme should allow for “soft” information about each transmitted bit or data symbol, rather than rely on packet erasures provided by an inner code or packet Cyclic Redundancy Check (CRC) scheme (as is usually the case for Raptor or LT codes). At the same time, the system should provide close-to-optimum utilization of channel capacity in a wide range of signal-to-noise ratios and channel conditions.